Minimizing total completion time on a batching machine with job processing time compatibilities
Identifieur interne : 002E83 ( Main/Exploration ); précédent : 002E82; suivant : 002E84Minimizing total completion time on a batching machine with job processing time compatibilities
Auteurs : Adrien Bellanger [France] ; Ammar Oulamara [France] ; Mikhail Y. Kovalyov [Biélorussie]Source :
English descriptors
Abstract
The problem of scheduling n jobs on an unbounded batching machine to minimize the total completion time is studied. The machine can process any number of jobs simultaneously in a batch, subject to an additional constraint that, in the same batch, the job processing times are compatible. There are given normal job pro- cessing times. An actual job processing time can exceed its normal value up to a certain percent. This percent is the same for all jobs. Thus, there are processing time intervals for the jobs. The job processing times are compatible if the corresponding processing time intervals intersect. The processing time of a batch is given by the longest processing time of the tasks in the batch and it correspnds to the left endpoint of the intersection of the job processing time intervals in this batch. For the total completion time a dynamic programming algorithm is provided.
Url:
DOI: 10.1016/j.endm.2010.05.164
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003193
- to stream Hal, to step Curation: 003193
- to stream Hal, to step Checkpoint: 002817
- to stream Main, to step Merge: 002F48
- to stream Main, to step Curation: 002E83
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Minimizing total completion time on a batching machine with job processing time compatibilities</title><author><name sortKey="Bellanger, Adrien" sort="Bellanger, Adrien" uniqKey="Bellanger A" first="Adrien" last="Bellanger">Adrien Bellanger</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-25312" status="INCOMING"><orgName>National Academy of Sciences of Belarus</orgName><orgName type="acronym">NATIONAL ACADEMY OF SCIENCES OF BELARUS</orgName><desc><address><country key="BY"></country></address></desc><listRelation><relation active="#struct-364760" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364760" type="direct"><org type="institution" xml:id="struct-364760" status="INCOMING"><orgName>BELARUS STATE UNIVERSITY</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Biélorussie</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00595669</idno><idno type="halId">hal-00595669</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-00595669</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-00595669</idno><idno type="doi">10.1016/j.endm.2010.05.164</idno><date when="2010">2010</date><idno type="wicri:Area/Hal/Corpus">003193</idno><idno type="wicri:Area/Hal/Curation">003193</idno><idno type="wicri:Area/Hal/Checkpoint">002817</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">002817</idno><idno type="wicri:Area/Main/Merge">002F48</idno><idno type="wicri:Area/Main/Curation">002E83</idno><idno type="wicri:Area/Main/Exploration">002E83</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Minimizing total completion time on a batching machine with job processing time compatibilities</title><author><name sortKey="Bellanger, Adrien" sort="Bellanger, Adrien" uniqKey="Bellanger A" first="Adrien" last="Bellanger">Adrien Bellanger</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-25312" status="INCOMING"><orgName>National Academy of Sciences of Belarus</orgName><orgName type="acronym">NATIONAL ACADEMY OF SCIENCES OF BELARUS</orgName><desc><address><country key="BY"></country></address></desc><listRelation><relation active="#struct-364760" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364760" type="direct"><org type="institution" xml:id="struct-364760" status="INCOMING"><orgName>BELARUS STATE UNIVERSITY</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Biélorussie</country></affiliation></author></analytic><idno type="DOI">10.1016/j.endm.2010.05.164</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Batching machine</term><term>compatibility constraints</term><term>dynamic programming</term><term>total completion time</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The problem of scheduling n jobs on an unbounded batching machine to minimize the total completion time is studied. The machine can process any number of jobs simultaneously in a batch, subject to an additional constraint that, in the same batch, the job processing times are compatible. There are given normal job pro- cessing times. An actual job processing time can exceed its normal value up to a certain percent. This percent is the same for all jobs. Thus, there are processing time intervals for the jobs. The job processing times are compatible if the corresponding processing time intervals intersect. The processing time of a batch is given by the longest processing time of the tasks in the batch and it correspnds to the left endpoint of the intersection of the job processing time intervals in this batch. For the total completion time a dynamic programming algorithm is provided.</div></front></TEI><affiliations><list><country><li>Biélorussie</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université de Lorraine</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Bellanger, Adrien" sort="Bellanger, Adrien" uniqKey="Bellanger A" first="Adrien" last="Bellanger">Adrien Bellanger</name></region><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name></country><country name="Biélorussie"><noRegion><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002E83 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002E83 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-00595669
|texte= Minimizing total completion time on a batching machine with job processing time compatibilities
}}
| This area was generated with Dilib version V0.6.33. |  |